package com.c2b.algorithm.leetcode.jzofferII;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/WGki4K/">只出现一次的数字 </a>
 * <p>给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。</p>
 * <pre>
 * 示例 1：
 *      输入：nums = [2,2,3,2]
 *      输出：3
 *
 * 示例 2：
 *      输入：nums = [0,1,0,1,0,1,100]
 *      输出：100
 * </pre>
 * <b>提示：</b>
 * <ui>
 * <li>1 <= nums.length <= 3 * 10^4</li>
 * <li>-2^31 <= nums[i] <= 2^31 - 1</li>
 * <li>nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次</li>
 * </ui>
 * <br>
 * 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * @author c2b
 * @since 2023/4/11 17:17
 */
public class Jz004SingleNumber_M {
    /**
     * hashmap
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> timesMap = new HashMap<>();
        for (int num : nums) {
            timesMap.put(num, timesMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : timesMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }

    /**
     * 排序
     */
    public int singleNumber2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // 对数组进行排序
        Arrays.sort(nums);
        // 出现三次的数字必定相邻，每次走三格
        for (int i = 0; i < nums.length - 1; i += 3) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        // 最后一位为只出现一次的数字
        return nums[nums.length - 1];
    }

    public static void main(String[] args) {
        Jz004SingleNumber_M jz004SingleNumber_m = new Jz004SingleNumber_M();
        int i = jz004SingleNumber_m.singleNumber2(new int[]{2,2,3,2});
        System.out.println(i);

    }
}
